package org.review.algorithm.recursion;

/**
 * 解8皇后思路：使用循环+递归
 * 关键步骤
 * 1、扫描当前落子的列是否已经存在子，arr[i]==curColumn
 * 2、关键是判断对角线位置不能有相同的皇后， 使用行=列的时候，等腰三角形的特性就明白了
 */
public class EightQueen {
    int[] arr;
    int maxSize;
    static int count = 0;

    public EightQueen(int maxSize) {
        this.maxSize = maxSize;
        this.arr = new int[maxSize];
    }

    public static void main(String[] args) {
        EightQueen eightQueen = new EightQueen(8);
        eightQueen.solve(0);
        System.out.println(count);
    }

    public void solve(int row) {
        if (row == maxSize) {
            count++;
            print();
        } else {
            for (int i = 0; i < maxSize; i++) {
            /*    arr[row] = i;
                if (isSafe(row)) {
                    solve(row + 1);
                }*/
                //TODO 2024/8/26:使用下面的方式， 看起来更好理解也更符号编码习惯
                if (isSafe(row, i)) {
                    arr[row] = i;
                    solve(row + 1);
                }
            }
        }
    }

    public boolean isSafe(int n) {
        for (int i = 0; i < n; i++) {
            if (arr[i] == arr[n] || Math.abs(n - i) == Math.abs(arr[n] - arr[i])) {
                return false;
            }
        }
        return true;
    }

    public boolean isSafe(int row, int col) {
        for (int i = 0; i < row; i++) {
            if (arr[i] == col || Math.abs(row - i) == Math.abs(col - arr[i])) {
                return false;
            }
        }
        return true;
    }

    private void print() {
        for (int i : arr) {
            System.out.print(i);
        }
        System.out.println();
    }
}
